/*
 * @lc app=leetcode id=146 lang=cpp
 *
 * [146] LRU Cache
 */
class LRUCache {
public:
    LRUCache(int capacity) 
        : cap(capacity), size(0) {
        
    }
    
    int get(int key) {

        if (kToIt.find(key) == kToIt.end()) {
            return -1;
        }

        kList.splice(kList.begin(), kList, kToIt[key]);
        kToIt[key] = kList.begin();
        return kToIt[key]->val;
    }
    
    void put(int key, int value) {

        if (kToIt.find(key) != kToIt.end()) {
            kList.splice(kList.begin(), kList, kToIt[key]);
            kToIt[key]->val = value;
            return ;
        }

        if (size >= cap) {
            auto it = kList.back();
            kToIt.erase(it.key);
            kList.pop_back();
            size--;
        } 

        kList.push_front(CacheNode(key, value));
        kToIt[key] = kList.begin();
        size++;
    }
private:
    struct CacheNode {
        int key;
        int val;
        CacheNode(const int k, const int v) : key(k), val(v) {}
    };
    unordered_map<int, std::list<CacheNode>::iterator> kToIt;
    std::list<CacheNode> kList;
    int cap;
    int size;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

